public class Solution {
    public int wiggleMaxLength(int[] nums) {
        int len = nums.length;

        if (len == 1) {
            return len;
        }

        //以i为结尾的最长摆动序列的长度
        int[] f = new int[len];//上升趋势
        int[] g = new int[len];//下降趋势

        //初始化
        for (int i = 0; i < len; i++) {
            f[i] = 1;
            g[i] = 1;
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    f[i] = Math.max(g[j] + 1, f[i]);
                } else if (nums[i] < nums[j]) {
                    g[i] = Math.max(f[j] + 1, g[i]);
                }
            }
        }

        int ret = 0;

        for (int i = 0; i < len; i++) {
            ret = Math.max(Math.max(ret, f[i]), g[i]);
        }

        return ret;
    }

    public int wiggleMaxLength2(int[] nums) {
        int len = nums.length;

        int count = 0;
        int left = 0;//左边的增长趋势
        int right = 0;//右边的增长趋势

        for (int i = 0; i < len - 1; i++) {
            right = nums[i] - nums[i + 1];
            if (right == 0) {
                continue;
            }
            if (left * right <= 0) {
                count++;
            }
            left = right;
        }

        return count + 1;
    }
}
